# 给你一个大小为 m x n 的网格和一个球。球的起始坐标为 [startRow, startColumn] 。你可以将球移到在四个方向上相邻的单元格内
# （可以穿过网格边界到达网格之外）。你 最多 可以移动 maxMove 次球。
#
#  给你五个整数 m、n、maxMove、startRow 以及 startColumn ，找出并返回可以将球移出边界的路径数量。因为答案可能非常大，返回对 10⁹ + 7 取余 后的结果。
#
#  示例 1：
# 输入：m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0
# 输出：6
#
#  示例 2：
# 输入：m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1
# 输出：12
class Solution:
    def findPaths2(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
        """
        动态规划
        动态规划的状态由移动次数、行和列决定，定义 dp[i][j][k] 表示球移动 i 次之后位于坐标 (j, k)的路径数量
        如果球移动了 i 次之后位于坐标 (j,k) ， 则移动第 i+1 次之后，球一定位于和坐标 (j,k) 相邻的一个坐标记为 (i', j')
            当 0 <= j' < m 且 0 <= k' < n时，球在移动 i+1 次之后没有出界， 将dp[i][j][k] 的值加到 dp[i+1][j'][k']；
            否则，球在第 i+1 次移动之后出界，将 dp[i][j][k] 的值加到出界的路径数
        :param m:
        :param n:
        :param maxMove:
        :param startRow:
        :param startColumn:
        :return:
        """
        MOD, res, directoins = 10 ** 9 + 7, 0, [(-1, 0), (1, 0), (0, -1), (0, 1)]
        dp = [[[0] * n for __ in range(m)] for _ in range(maxMove + 1)]
        dp[0][startRow][startColumn] = 1  # 一次都不移动就在原位置(状态初始化)
        for i in range(maxMove):
            for j in range(m):
                for k in range(n):
                    if dp[i][j][k] > 0:  # 通过移动 i 次可以到达位置(j, k)
                        for dx, dy in directoins:  # 尝试向相邻的位置进行移动
                            tmpX, tmpY = j + dx, k + dy
                            if 0 <= tmpX < m and 0 <= tmpY < n:  # 下一次移动未移动到界外，就需要更新通过移动i + 1 次可以到达(tmpX, tmpY)的路径数
                                dp[i + 1][tmpX][tmpY] = (dp[i + 1][tmpX][tmpY] + dp[i][j][k]) % MOD
                            else:  # 下一次移动就到了界外，则需要更新结果
                                res = (res + dp[i][j][k]) % MOD
        return res % MOD

    def findPaths1(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
        """
        解法一：回溯法(超时)
        :param m:
        :param n:
        :param maxMove:
        :param startRow:
        :param startColumn:
        :return:
        """
        res, directions = 0, [(-1, 0), (1, 0), (0, -1), (0, 1)]

        def dfs(curPosX: int, curPosY: int, remainMoveCount: int) -> None:
            # 移动出了边界且剩余移动次数大于等于 0 ， 说明本次移动路径可以移出边界
            if (curPosX == -1 or curPosX == m or curPosY == -1 or curPosY == n) and remainMoveCount >= 0:
                nonlocal res
                res += 1
                return
            if remainMoveCount == 0:  # 不可以移动了，返回
                return
            for x, y in directions:  # 尝试朝四个方向进行移动
                dfs(curPosX + x, curPosY + y, remainMoveCount - 1)

        dfs(startRow, startColumn, maxMove)
        return res % (10 ** 9 + 7)

    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
        return self.findPaths2(m, n, maxMove, startRow, startColumn)


if __name__ == "__main__":
    m, n, maxMove, startRow, startColumn = 1, 3, 3, 0, 1
    m, n, maxMove, startRow, startColumn = 2, 2, 2, 0, 0
    m, n, maxMove, startRow, startColumn = 8, 7, 16, 1, 5
    print(Solution().findPaths(m, n, maxMove, startRow, startColumn))
